package com.kobeliu.entity;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/9 10:20
 */

import java.util.*;

/**
 * 树 的 前中后序遍历
 */
public class Demo_75_No_144_145_94 {

    //树的结构
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }

    public static List<Integer> Traversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        //preOrder(root,list); //前序遍历 中左右
        //inOrder(root,list); //中序遍历 左中右
        postOrder(root,list); //后序遍历 左右中
        return list;

    }

    //递归中序遍历
    //左中右
    private static void inOrder(TreeNode root, List<Integer> list) {
        if(root==null) return;
        if(root.left!=null) inOrder(root.left,list);
        list.add(root.val);
        if(root.right!=null) inOrder(root.right,list);
    }

    //递归前序遍历
    //中左右
    private static void preOrder(TreeNode root,List<Integer> list) {
        if(root==null) return;
        list.add(root.val);
        if(root.left!=null) preOrder(root.left,list);
        if(root.right!=null) preOrder(root.right,list);
    }

    //递归后序遍历
    //左右中
    private static void postOrder(TreeNode root,List<Integer> list) {
        if(root==null) return;
        if(root.left!=null) postOrder(root.left,list);
        if(root.right!=null) postOrder(root.right,list);
        list.add(root.val);
    }

    //前序遍历 非递归
    //中左右
    private static List<Integer> preOrderNoRecursion(TreeNode root,List<Integer> list) {
        Deque<TreeNode> trees = new LinkedList<>();
//        trees.push(root);
        TreeNode t = root;
        while(!trees.isEmpty() || t!=null){
            while(t!=null){
                list.add(t.val);
                trees.push(t);
                t = t.left;
            }
            t = trees.pop();
            t = t.right;
        }
        return list;
    }

    //后序遍历 非递归
    //左右中
    private static List<Integer> postOrderNoRecursion(TreeNode root,List<Integer> list) {
        Deque<TreeNode> trees = new LinkedList<>();
//        trees.push(root);
        TreeNode t = null;
        while(!trees.isEmpty() || t!=null){
            while(t!=null){
                trees.push(root);
                root = root.left;
            }
            root = trees.pop();
            if (root.right == null || root.right == t) {
                list.add(root.val);
                t = root;
                root = null;
            } else {
                trees.push(root);
                root = root.right;
            }
        }
        return list;
    }

    //前序遍历
    //中左右
//    private static List<Integer> inOrderNoRecursion(TreeNode root,List<Integer> list) {
//
//    }
}
